转到题目

正确的贪心思路解析

我们按照您的思路进行详细的讲解和代码实现，分为以下几个步骤：

思路分析

目标：最少删除次数：
- 我们的目标是删除两个数组中的元素，使得每个数组只保留唯一的元素。
- 但是，如果有重复元素，显然需要删除其中一些，这时我们采用贪心策略，尽量选择少删除，优先保留独立元素。
首先处理每个数组内部的重复元素：
- 对于每个数组内，删除重复的元素。比如，数组中如果某个元素出现超过一次，那么我们需要删除其中的多余部分。
- 假设数组 A 删除的次数为 v1，数组 B 删除的次数为 v2。
合并两个数组：公共元素：
- 合并后的两个数组中，可能有公共元素。此时，删除公共元素时可以选择删除其中一个数组中的元素，而另一个数组中的该元素不需要删除。
- 由于删除公共元素是任意的，因此我们可以灵活选择。
多余的删除操作：
- 假设处理完每个数组内的重复元素后，数组 A 和数组 B 可能会有不等的删除次数。我们用 |v1 - v2| 来表示这种差异。
- 通过公共元素的删除，我们希望减少这种差异，如果差异太大，那么就需要多次操作来平衡。
最终答案：
- 最终的删除次数是： \(\text{res} = \max(v1, v2) + \frac{\max(0, \text{具有重复元素对的数量} - |v1 - v2| +1)}{2}\)
- 这个公式的意思是，初始的删除次数是 max(v1, v2)，然后通过公共元素的优化，如果有多余的删除操作，可以通过公共元素减少多余的操作次数，最终得到最少的删除次数。

代码实现

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, int> arr_1(0), arr_2(0);
int n;
void solve (){
    cin >> n;
    int tem;
    for (int i = 0; i < n; i++) {
        cin >> tem;
        arr_1[tem] ++;
    }
    for (int i = 0; i < n; i++) {
        cin >> tem;
        arr_2[tem]++;
    }
    int v1, v2;
    v1 = 0, v2 = 0;
    for (auto it : arr_1) {
        v1 += max(it.second-1,0);
        if (it.second > 1)arr_1[it.first] = 1;
    }
    for (auto it : arr_2) {
        v2 += max(it.second - 1, 0);
        if (it.second > 1)arr_2[it.first] = 1;
    }
    for (auto it : arr_2) {
        arr_1[it.first] += it.second;
    }
    int x = 0;
    for (auto it : arr_1) {
        if (it.second == 2)x++;
    }
    int res = max(v1, v2) + max(0, (x - abs(v1 - v2)+1) / 2);
    cout << res;
}
int main()
{

    solve();

    return 0;
    }

代码详细讲解

输入和计数：
- 我们通过 map<int, int> 来统计数组中每个元素的出现次数。cnt[i][x] 记录第 i 个数组中元素 x 的出现次数。
计算删除次数 (v1, v2)：
- 对于每个数组 i，我们遍历 cnt[i] 中的元素，计算多余的重复元素的数量。若某元素出现次数大于1，我们就要删除 it.second - 1 个该元素。并且将该元素的出现次数设为1，表示去重。
- v[i] 保存每个数组需要删除的元素个数。v1 和 v2 分别代表数组A和数组B中的删除次数。
计算公共元素数量：
- 我们计算两个数组中共同元素的数量 common_count。这通过遍历数组A的所有元素，然后检查它们是否也在数组B中存在。
计算最终结果：
- 初始答案为 max(v1, v2)，即最多的删除次数。然后，我们用公共元素数量来弥补多余的删除次数。
- 通过 (common_count - extra +1) / 2，我们计算可以用多少公共元素来减少多余的删除操作。extra 表示 |v1 - v2|，即两数组删除次数的差异。
输出结果：
- 最终的删除次数是 max(v1, v2) 加上公共元素可以弥补的次数。

复杂度分析

时间复杂度：O(n)，我们需要遍历每个数组的元素进行计数，并且遍历公共元素进行合并计算。
空间复杂度：O(n)，我们使用了 map 来存储每个元素的计数。

总结

通过这种贪心算法，我们可以在删除元素的过程中尽量减少操作次数。首先通过处理每个数组内部的重复元素，然后通过公共元素的合并来进一步优化删除次数。最终得出的最少删除次数是通过精确计算和合理的选择来得到的。

返回

转到题目

正确的贪心思路解析

思路分析

代码实现

代码详细讲解

复杂度分析

总结